package BasicClass.Two;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Two_14 {
    public static void main(String[] args) throws IOException {
        Two_14 two14 = new Two_14();
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        while (!bufferedReader.ready()){
            int size = Integer.parseInt(bufferedReader.readLine());
            String[] strings = bufferedReader.readLine().split(" ");
            int[] arr = new int[size];
            for (int i = 0;i<size;i++) {
                arr[i] = Integer.parseInt(strings[i]);
            }
            int flag = Integer.parseInt(bufferedReader.readLine());
            two14.Sort(arr,0,size-1,flag);
            StringBuilder builder = new StringBuilder();
            for (int i : arr) {
                builder.append(i+" ");
            }
            System.out.println(builder);
        }
    }

    /**
     * 输入整型数组和排序标识，对其元素按照升序或降序进行排序（一组测试用例可能会有多组数据）
     * 第一行输入数组元素个数
     * 第二行输入待排序的数组，每个数用空格隔开
     * 第三行输入一个整数0或1。0代表升序排序，1代表降序排序
     */
    public void Sort(int[] arr,int L,int R,int flag){
        if(L < R){
            swap(arr, L+(int) (Math.random()*(R-L+1)),R);
            if(flag==0){
                int[] ints = partition1(arr, L, R);
                Sort(arr,L,ints[0]-1,flag);
                Sort(arr,ints[1]+1,R,flag);
            }else {
                int[] ints = partition2(arr, L, R);
                Sort(arr,L,ints[0]-1,flag);
                Sort(arr,ints[1]+1,R,flag);
            }
        }
    }

    public int[] partition1(int[] arr,int L,int R){
        int less = L - 1;
        int more = R;
        while (L < more){
            if(arr[L] > arr[R]){
                swap(arr,L,--more);
            }else if(arr[L] < arr[R]){
                swap(arr,L++,++less);
            }else {
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }

    public int[] partition2(int[] arr,int L,int R){
        int less = L - 1;
        int more = R;
        while (L < more){
            if(arr[L] < arr[R]){
                swap(arr,L,--more);
            }else if(arr[L] > arr[R]){
                swap(arr,L++,++less);
            }else {
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
